/*
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 */
package net.sf.l2j.gameserver;

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.LineNumberReader;
import java.io.RandomAccessFile;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.nio.IntBuffer;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.logging.Logger;

import javolution.util.FastMap;
import net.sf.l2j.Config;
import net.sf.l2j.gameserver.datatables.DoorTable;
import net.sf.l2j.gameserver.model.L2Object;
import net.sf.l2j.gameserver.model.L2World;
import net.sf.l2j.gameserver.model.Location;
import net.sf.l2j.gameserver.model.actor.instance.L2DoorInstance;
import net.sf.l2j.gameserver.model.actor.instance.L2FortSiegeGuardInstance;
import net.sf.l2j.gameserver.model.actor.instance.L2PcInstance;
import net.sf.l2j.gameserver.model.actor.instance.L2SiegeGuardInstance;
import net.sf.l2j.util.Point3D;

/**
 * @author -Nemesiss-
 */
public class GeoEngine extends GeoData {
	private static Logger _log = Logger.getLogger(GeoData.class.getName());
	private static GeoEngine _instance;
	private final static byte _e = 1;
	private final static byte _w = 2;
	private final static byte _s = 4;
	private final static byte _n = 8;
	private static Map<Short, MappedByteBuffer> _geodata = new FastMap<Short, MappedByteBuffer>();
	private static Map<Short, IntBuffer> _geodataIndex = new FastMap<Short, IntBuffer>();
	private static BufferedOutputStream _geoBugsOut;

	public static GeoEngine getInstance() {
		if (_instance == null)
			_instance = new GeoEngine();
		return _instance;
	}

	public GeoEngine() {
		nInitGeodata();
	}

	// Public Methods
	/**
	 * @see net.sf.l2j.gameserver.GeoData#getType(int, int)
	 */
	@Override
	public short getType(int x, int y) {
		return nGetType(x - L2World.MAP_MIN_X >> 4, y - L2World.MAP_MIN_Y >> 4);
	}

	/**
	 * @see net.sf.l2j.gameserver.GeoData#getHeight(int, int, int)
	 */
	@Override
	public short getHeight(int x, int y, int z) {
		return nGetHeight(x - L2World.MAP_MIN_X >> 4,
				y - L2World.MAP_MIN_Y >> 4, z);
	}

	/**
	 * @see net.sf.l2j.gameserver.GeoData#getSpawnHeight(int, int, int, int,
	 *      int)
	 */
	@Override
	public short getSpawnHeight(int x, int y, int zmin, int zmax, int spawnid) {
		return nGetSpawnHeight(x - L2World.MAP_MIN_X >> 4, y
				- L2World.MAP_MIN_Y >> 4, zmin, zmax, spawnid);
	}

	/**
	 * @see net.sf.l2j.gameserver.GeoData#geoPosition(int, int)
	 */
	@Override
	public String geoPosition(int x, int y) {
		int gx = x - L2World.MAP_MIN_X >> 4;
		int gy = y - L2World.MAP_MIN_Y >> 4;
		return "bx: " + getBlock(gx) + " by: " + getBlock(gy) + " cx: "
				+ getCell(gx) + " cy: " + getCell(gy) + "  region offset: "
				+ getRegionOffset(gx, gy);
	}

	/**
	 * @see net.sf.l2j.gameserver.GeoData#canSeeTarget(L2Object, Point3D)
	 */
	@Override
	public boolean canSeeTarget(L2Object cha, Point3D target) {
		if (cha.getZ() >= target.getZ())
			return canSeeTarget(cha.getX(), cha.getY(), cha.getZ(),
					target.getX(), target.getY(), target.getZ());
		else
			return canSeeTarget(target.getX(), target.getY(), target.getZ(),
					cha.getX(), cha.getY(), cha.getZ());
	}

	/**
	 * @see net.sf.l2j.gameserver.GeoData#canSeeTarget(net.sf.l2j.gameserver.model.L2Object,
	 *      net.sf.l2j.gameserver.model.L2Object)
	 */
	@Override
	public boolean canSeeTarget(L2Object cha, L2Object target) {
		// To be able to see over fences and give the player the viewpoint
		// game client has, all coordinates are lifted 45 from ground.
		// Because of layer selection in LOS algorithm (it selects -45 there
		// and some layers can be very close...) do not change this without
		// changing the LOS code.
		// Basically the +45 is character height. Raid bosses are naturally
		// higher,
		// dwarves shorter, but this should work relatively well.
		// If this is going to be improved, use e.g.
		// ((L2Character)cha).getTemplate().collisionHeight
		int z = cha.getZ() + 45;
		if (cha instanceof L2SiegeGuardInstance
				&& cha instanceof L2FortSiegeGuardInstance)
			z += 30; // well they don't move closer to balcony fence at the
		// moment :(
		int z2 = target.getZ() + 45;
		if (!(target instanceof L2DoorInstance)
				&& DoorTable.getInstance().checkIfDoorsBetween(cha.getX(),
						cha.getY(), z, target.getX(), target.getY(), z2))
			return false;
		if (target instanceof L2DoorInstance)
			return true; // door coordinates are hinge coords..
		if (target instanceof L2SiegeGuardInstance
				&& target instanceof L2FortSiegeGuardInstance)
			z2 += 30; // well they don't move closer to balcony fence at the
		// moment :(
		if (cha.getZ() >= target.getZ())
			return canSeeTarget(cha.getX(), cha.getY(), z, target.getX(),
					target.getY(), z2);
		else
			return canSeeTarget(target.getX(), target.getY(), z2, cha.getX(),
					cha.getY(), z);
	}

	/**
	 * @see net.sf.l2j.gameserver.GeoData#canSeeTargetDebug(net.sf.l2j.gameserver.model.actor.instance.L2PcInstance,
	 *      net.sf.l2j.gameserver.model.L2Object)
	 */
	@Override
	public boolean canSeeTargetDebug(L2PcInstance gm, L2Object target) {
		// comments: see above
		int z = gm.getZ() + 45;
		int z2 = target.getZ() + 45;
		if (target instanceof L2DoorInstance) {
			gm.sendMessage("door always true");
			return true; // door coordinates are hinge coords..
		}
		if (gm.getZ() >= target.getZ())
			return canSeeDebug(gm, gm.getX() - L2World.MAP_MIN_X >> 4,
					gm.getY() - L2World.MAP_MIN_Y >> 4, z, target.getX()
							- L2World.MAP_MIN_X >> 4, target.getY()
							- L2World.MAP_MIN_Y >> 4, z2);
		else
			return canSeeDebug(gm, target.getX() - L2World.MAP_MIN_X >> 4,
					target.getY() - L2World.MAP_MIN_Y >> 4, z2, gm.getX()
							- L2World.MAP_MIN_X >> 4, gm.getY()
							- L2World.MAP_MIN_Y >> 4, z);
	}

	/**
	 * @see net.sf.l2j.gameserver.GeoData#getNSWE(int, int, int)
	 */
	@Override
	public short getNSWE(int x, int y, int z) {
		return nGetNSWE(x - L2World.MAP_MIN_X >> 4, y - L2World.MAP_MIN_Y >> 4,
				z);
	}

	/**
	 * @see net.sf.l2j.gameserver.GeoData#moveCheck(int, int, int, int, int,
	 *      int)
	 */
	@Override
	public Location moveCheck(int x, int y, int z, int tx, int ty, int tz) {
		Location startpoint = new Location(x, y, z);
		if (DoorTable.getInstance().checkIfDoorsBetween(x, y, z, tx, ty, tz))
			return startpoint;
		Location destiny = new Location(tx, ty, tz);
		return moveCheck(startpoint, destiny, x - L2World.MAP_MIN_X >> 4, y
				- L2World.MAP_MIN_Y >> 4, z, tx - L2World.MAP_MIN_X >> 4, ty
				- L2World.MAP_MIN_Y >> 4, tz);
	}

	/**
	 * @see net.sf.l2j.gameserver.GeoData#addGeoDataBug(net.sf.l2j.gameserver.model.actor.instance.L2PcInstance,
	 *      java.lang.String)
	 */
	@Override
	public void addGeoDataBug(L2PcInstance gm, String comment) {
		int gx = gm.getX() - L2World.MAP_MIN_X >> 4;
		int gy = gm.getY() - L2World.MAP_MIN_Y >> 4;
		int bx = getBlock(gx);
		int by = getBlock(gy);
		int cx = getCell(gx);
		int cy = getCell(gy);
		int rx = (gx >> 11) + 16;
		int ry = (gy >> 11) + 10;
		String out = rx + ";" + ry + ";" + bx + ";" + by + ";" + cx + ";" + cy
				+ ";" + gm.getZ() + ";" + comment + "\n";
		try {
			_geoBugsOut.write(out.getBytes());
			_geoBugsOut.flush();
			gm.sendMessage("GeoData bug saved!");
		} catch (Exception e) {
			e.printStackTrace();
			gm.sendMessage("GeoData bug save Failed!");
		}
	}

	// Private Methods
	private boolean canSeeTarget(int x, int y, int z, int tx, int ty, int tz) {
		return canSee(x - L2World.MAP_MIN_X >> 4, y - L2World.MAP_MIN_Y >> 4,
				z, tx - L2World.MAP_MIN_X >> 4, ty - L2World.MAP_MIN_Y >> 4, tz);
	}

	private static boolean canSee(int x, int y, double z, int tx, int ty, int tz) {
		int dx = tx - x;
		int dy = ty - y;
		final double dz = tz - z;
		final int distance2 = dx * dx + dy * dy;
		if (distance2 > 90000)
			return false; // Avoid too long check
		else if (distance2 < 82) {
			// 200 too deep/high. This value should be in sync with NLOS
			if (dz * dz > 40000) {
				short region = getRegionOffset(x, y);
				// geodata is loaded for region and mobs should have correct Z
				// coordinate...
				// so there would likely be a floor in between the two
				if (_geodata.get(region) != null)
					return false;
			}
			return true;
		}
		// Increment in Z coordinate when moving along X or Y axis
		// and not straight to the target. This is done because
		// calculation moves either in X or Y direction.
		final int inc_x = sign(dx);
		final int inc_y = sign(dy);
		dx = Math.abs(dx);
		dy = Math.abs(dy);
		final double inc_z_directionx = dz * dx / distance2;
		final double inc_z_directiony = dz * dy / distance2;
		// next_* are used in NLOS check from x,y
		int next_x = x;
		int next_y = y;
		// creates path to the target
		// calculation stops when next_* == target
		if (dx >= dy)// dy/dx <= 1
		{
			int delta_A = 2 * dy;
			int d = delta_A - dx;
			int delta_B = delta_A - 2 * dx;
			for (int i = 0; i < dx; i++) {
				x = next_x;
				y = next_y;
				if (d > 0) {
					d += delta_B;
					next_x += inc_x;
					z += inc_z_directionx;
					next_y += inc_y;
					z += inc_z_directiony;
					// _log.warning("1: next_x:"+next_x+" next_y"+next_y);
					if (!nLOS(x, y, (int) z, inc_x, inc_y, tz, false))
						return false;
				} else {
					d += delta_A;
					next_x += inc_x;
					// _log.warning("2: next_x:"+next_x+" next_y"+next_y);
					z += inc_z_directionx;
					if (!nLOS(x, y, (int) z, inc_x, 0, tz, false))
						return false;
				}
			}
		} else {
			int delta_A = 2 * dx;
			int d = delta_A - dy;
			int delta_B = delta_A - 2 * dy;
			for (int i = 0; i < dy; i++) {
				x = next_x;
				y = next_y;
				if (d > 0) {
					d += delta_B;
					next_y += inc_y;
					z += inc_z_directiony;
					next_x += inc_x;
					z += inc_z_directionx;
					// _log.warning("3: next_x:"+next_x+" next_y"+next_y);
					if (!nLOS(x, y, (int) z, inc_x, inc_y, tz, false))
						return false;
				} else {
					d += delta_A;
					next_y += inc_y;
					// _log.warning("4: next_x:"+next_x+" next_y"+next_y);
					z += inc_z_directiony;
					if (!nLOS(x, y, (int) z, 0, inc_y, tz, false))
						return false;
				}
			}
		}
		return true;
	}

	/*
	 * Debug function for checking if there's a line of sight between two
	 * coordinates. Creates points for line of sight check (x,y,z towards
	 * target) and in each point, layer and movement checks are made with NLOS
	 * function. Coordinates here are geodata x,y but z coordinate is world
	 * coordinate
	 */
	private static boolean canSeeDebug(L2PcInstance gm, int x, int y, double z,
			int tx, int ty, int tz) {
		int dx = tx - x;
		int dy = ty - y;
		final double dz = tz - z;
		final int distance2 = dx * dx + dy * dy;
		if (distance2 > 90000) // (300*300) 300*16 = 4800 in world coord
		{
			// Avoid too long check
			gm.sendMessage("dist > 300");
			return false;
		}
		// very short checks: 9 => 144 world distance
		// this ensures NLOS function has enough points to calculate,
		// it might not work when distance is small and path vertical
		else if (distance2 < 82) {
			// 200 too deep/high. This value should be in sync with NLOS
			if (dz * dz > 40000) {
				short region = getRegionOffset(x, y);
				// geodata is loaded for region and mobs should have correct Z
				// coordinate...
				// so there would likely be a floor in between the two
				if (_geodata.get(region) != null)
					return false;
			}
			return true;
		}
		// Increment in Z coordinate when moving along X or Y axis
		// and not straight to the target. This is done because
		// calculation moves either in X or Y direction.
		final int inc_x = sign(dx);
		final int inc_y = sign(dy);
		dx = Math.abs(dx);
		dy = Math.abs(dy);
		final double inc_z_directionx = dz * dx / distance2;
		final double inc_z_directiony = dz * dy / distance2;
		gm.sendMessage("Los: from X: " + x + "Y: " + y + "--->> X: " + tx
				+ " Y: " + ty);
		// next_* are used in NLOS check from x,y
		int next_x = x;
		int next_y = y;
		// creates path to the target
		// calculation stops when next_* == target
		if (dx >= dy)// dy/dx <= 1
		{
			int delta_A = 2 * dy;
			int d = delta_A - dx;
			int delta_B = delta_A - 2 * dx;
			for (int i = 0; i < dx; i++) {
				x = next_x;
				y = next_y;
				if (d > 0) {
					d += delta_B;
					next_x += inc_x;
					z += inc_z_directionx;
					next_y += inc_y;
					z += inc_z_directiony;
					// _log.warning("1: next_x:"+next_x+" next_y"+next_y);
					if (!nLOS(x, y, (int) z, inc_x, inc_y, tz, true))
						return false;
				} else {
					d += delta_A;
					next_x += inc_x;
					// _log.warning("2: next_x:"+next_x+" next_y"+next_y);
					z += inc_z_directionx;
					if (!nLOS(x, y, (int) z, inc_x, 0, tz, true))
						return false;
				}
			}
		} else {
			int delta_A = 2 * dx;
			int d = delta_A - dy;
			int delta_B = delta_A - 2 * dy;
			for (int i = 0; i < dy; i++) {
				x = next_x;
				y = next_y;
				if (d > 0) {
					d += delta_B;
					next_y += inc_y;
					z += inc_z_directiony;
					next_x += inc_x;
					z += inc_z_directionx;
					// _log.warning("3: next_x:"+next_x+" next_y"+next_y);
					if (!nLOS(x, y, (int) z, inc_x, inc_y, tz, true))
						return false;
				} else {
					d += delta_A;
					next_y += inc_y;
					// _log.warning("4: next_x:"+next_x+" next_y"+next_y);
					z += inc_z_directiony;
					if (!nLOS(x, y, (int) z, 0, inc_y, tz, true))
						return false;
				}
			}
		}
		return true;
	}

	/*
	 * MoveCheck
	 */
	private static Location moveCheck(Location startpoint, Location destiny,
			int x, int y, double z, int tx, int ty, int tz) {
		int dx = tx - x;
		int dy = ty - y;
		final int distance2 = dx * dx + dy * dy;
		if (distance2 == 0)
			return destiny;
		if (distance2 > 36100) // 190*190*16 = 3040 world coord
		{
			// Avoid too long check
			// Currently we calculate a middle point
			// for wyvern users and otherwise for comfort
			double divider = Math.sqrt((double) 30000 / distance2);
			tx = x + (int) (divider * dx);
			ty = y + (int) (divider * dy);
			int dz = tz - startpoint.getZ();
			tz = startpoint.getZ() + (int) (divider * dz);
			dx = tx - x;
			dy = ty - y;
			// return startpoint;
		}
		// Increment in Z coordinate when moving along X or Y axis
		// and not straight to the target. This is done because
		// calculation moves either in X or Y direction.
		final int inc_x = sign(dx);
		final int inc_y = sign(dy);
		dx = Math.abs(dx);
		dy = Math.abs(dy);
		// gm.sendMessage("MoveCheck: from X: "+x+ "Y: "+y+
		// "--->> X: "+tx+" Y: "+ty);
		// next_* are used in NcanMoveNext check from x,y
		int next_x = x;
		int next_y = y;
		double tempz = z;
		// creates path to the target, using only x or y direction
		// calculation stops when next_* == target
		if (dx >= dy)// dy/dx <= 1
		{
			int delta_A = 2 * dy;
			int d = delta_A - dx;
			int delta_B = delta_A - 2 * dx;
			for (int i = 0; i < dx; i++) {
				x = next_x;
				y = next_y;
				if (d > 0) {
					d += delta_B;
					next_x += inc_x;
					next_y += inc_y;
					// _log.warning("2: next_x:"+next_x+" next_y"+next_y);
					tempz = nCanMoveNext(x, y, (int) z, next_x, next_y, tz);
					if (tempz == Double.MIN_VALUE)
						return new Location((x << 4) + L2World.MAP_MIN_X,
								(y << 4) + L2World.MAP_MIN_Y, (int) z);
					else
						z = tempz;
				} else {
					d += delta_A;
					next_x += inc_x;
					// _log.warning("3: next_x:"+next_x+" next_y"+next_y);
					tempz = nCanMoveNext(x, y, (int) z, next_x, next_y, tz);
					if (tempz == Double.MIN_VALUE)
						return new Location((x << 4) + L2World.MAP_MIN_X,
								(y << 4) + L2World.MAP_MIN_Y, (int) z);
					else
						z = tempz;
				}
			}
		} else {
			int delta_A = 2 * dx;
			int d = delta_A - dy;
			int delta_B = delta_A - 2 * dy;
			for (int i = 0; i < dy; i++) {
				x = next_x;
				y = next_y;
				if (d > 0) {
					d += delta_B;
					next_y += inc_y;
					next_x += inc_x;
					// _log.warning("5: next_x:"+next_x+" next_y"+next_y);
					tempz = nCanMoveNext(x, y, (int) z, next_x, next_y, tz);
					if (tempz == Double.MIN_VALUE)
						return new Location((x << 4) + L2World.MAP_MIN_X,
								(y << 4) + L2World.MAP_MIN_Y, (int) z);
					else
						z = tempz;
				} else {
					d += delta_A;
					next_y += inc_y;
					// _log.warning("6: next_x:"+next_x+" next_y"+next_y);
					tempz = nCanMoveNext(x, y, (int) z, next_x, next_y, tz);
					if (tempz == Double.MIN_VALUE)
						return new Location((x << 4) + L2World.MAP_MIN_X,
								(y << 4) + L2World.MAP_MIN_Y, (int) z);
					else
						z = tempz;
				}
			}
		}
		return destiny; // should actually return correct z here instead of tz
	}

	private static byte sign(int x) {
		if (x >= 0)
			return +1;
		else
			return -1;
	}

	// GeoEngine
	private static void nInitGeodata() {
		LineNumberReader lnr = null;
		try {
			_log.info("Geo Engine: - Loading Geodata...");
			File Data = new File("./data/geodata/geo_index.txt");
			if (!Data.exists())
				return;
			lnr = new LineNumberReader(new BufferedReader(new FileReader(Data)));
		} catch (Exception e) {
			e.printStackTrace();
			throw new Error("Failed to Load geo_index File.");
		}
		String line;
		try {
			while ((line = lnr.readLine()) != null) {
				if (line.trim().length() == 0)
					continue;
				StringTokenizer st = new StringTokenizer(line, "_");
				byte rx = Byte.parseByte(st.nextToken());
				byte ry = Byte.parseByte(st.nextToken());
				loadGeodataFile(rx, ry);
			}
		} catch (Exception e) {
			e.printStackTrace();
			throw new Error("Failed to Read geo_index File.");
		}
		try {
			File geo_bugs = new File("./data/geodata/geo_bugs.txt");
			_geoBugsOut = new BufferedOutputStream(new FileOutputStream(
					geo_bugs, true));
		} catch (Exception e) {
			e.printStackTrace();
			throw new Error("Failed to Load geo_bugs.txt File.");
		}
	}

	public static void unloadGeodata(byte rx, byte ry) {
		short regionoffset = (short) ((rx << 5) + ry);
		_geodataIndex.remove(regionoffset);
		_geodata.remove(regionoffset);
	}

	public static boolean loadGeodataFile(byte rx, byte ry) {
		String fname = "./data/geodata/" + rx + "_" + ry + ".l2j";
		short regionoffset = (short) ((rx << 5) + ry);
		_log.info("Geo Engine: - Loading: " + fname + " -> region offset: "
				+ regionoffset + "X: " + rx + " Y: " + ry);
		File Geo = new File(fname);
		int size, index = 0, block = 0, flor = 0;
		try {
			// Create a read-only memory-mapped file
			FileChannel roChannel = new RandomAccessFile(Geo, "r").getChannel();
			size = (int) roChannel.size();
			MappedByteBuffer geo;
			if (Config.FORCE_GEODATA)
				// it is not guarantee, because the underlying operating system
				// may have paged out some of the buffer's data
				geo = roChannel.map(FileChannel.MapMode.READ_ONLY, 0, size)
						.load();
			else
				geo = roChannel.map(FileChannel.MapMode.READ_ONLY, 0, size);
			geo.order(ByteOrder.LITTLE_ENDIAN);
			if (size > 196608) {
				// Indexing geo files, so we will know where each block starts
				IntBuffer indexs = IntBuffer.allocate(65536);
				while (block < 65536) {
					byte type = geo.get(index);
					indexs.put(block, index);
					block++;
					index++;
					if (type == 0)
						index += 2; // 1x short
					else if (type == 1)
						index += 128; // 64 x short
					else {
						int b;
						for (b = 0; b < 64; b++) {
							byte layers = geo.get(index);
							index += (layers << 1) + 1;
							if (layers > flor)
								flor = layers;
						}
					}
				}
				_geodataIndex.put(regionoffset, indexs);
			}
			_geodata.put(regionoffset, geo);
			_log.info("Geo Engine: - Max Layers: " + flor + " Size: " + size
					+ " Loaded: " + index);
		} catch (Exception e) {
			e.printStackTrace();
			_log.warning("Failed to Load GeoFile at block: " + block + "\n");
			return false;
		}
		return true;
	}

	// Geodata Methods
	/**
	 * @param x
	 * @param y
	 * @return Region Offset
	 */
	private static short getRegionOffset(int x, int y) {
		int rx = x >> 11; // =/(256 * 8)
		int ry = y >> 11;
		return (short) ((rx + 16 << 5) + ry + 10);
	}

	/**
	 * @param pos
	 * @return Block Index: 0-255
	 */
	private static int getBlock(int geo_pos) {
		return (geo_pos >> 3) % 256;
	}

	/**
	 * @param pos
	 * @return Cell Index: 0-7
	 */
	private static int getCell(int geo_pos) {
		return geo_pos % 8;
	}

	// Geodata Functions
	/**
	 * @param x
	 * @param y
	 * @return Type of geo_block: 0-2
	 */
	private static short nGetType(int x, int y) {
		short region = getRegionOffset(x, y);
		int blockX = getBlock(x);
		int blockY = getBlock(y);
		int index = 0;
		// Geodata without index - it is just empty so index can be calculated
		// on the fly
		if (_geodataIndex.get(region) == null)
			index = ((blockX << 8) + blockY) * 3;
		// Get Index for current block of current geodata region
		else
			index = _geodataIndex.get(region).get((blockX << 8) + blockY);
		// Buffer that Contains current Region GeoData
		ByteBuffer geo = _geodata.get(region);
		if (geo == null) {
			if (Config.DEBUG)
				_log.warning("Geo Region - Region Offset: " + region
						+ " dosnt exist!!");
			return 0;
		}
		return geo.get(index);
	}

	/**
	 * @param x
	 * @param y
	 * @param z
	 * @return Nearlest Z
	 */
	private static short nGetHeight(int geox, int geoy, int z) {
		short region = getRegionOffset(geox, geoy);
		int blockX = getBlock(geox);
		int blockY = getBlock(geoy);
		int cellX, cellY, index;
		// Geodata without index - it is just empty so index can be calculated
		// on the fly
		if (_geodataIndex.get(region) == null)
			index = ((blockX << 8) + blockY) * 3;
		// Get Index for current block of current region geodata
		else
			index = _geodataIndex.get(region).get((blockX << 8) + blockY);
		// Buffer that Contains current Region GeoData
		ByteBuffer geo = _geodata.get(region);
		if (geo == null) {
			if (Config.DEBUG)
				_log.warning("Geo Region - Region Offset: " + region
						+ " dosnt exist!!");
			return (short) z;
		}
		// Read current block type: 0-flat,1-complex,2-multilevel
		byte type = geo.get(index);
		index++;
		if (type == 0)
			return geo.getShort(index);
		else if (type == 1)// complex
		{
			cellX = getCell(geox);
			cellY = getCell(geoy);
			index += (cellX << 3) + cellY << 1;
			short height = geo.getShort(index);
			height = (short) (height & 0x0fff0);
			height = (short) (height >> 1); // height / 2
			return height;
		} else
		// multilevel
		{
			cellX = getCell(geox);
			cellY = getCell(geoy);
			int offset = (cellX << 3) + cellY;
			while (offset > 0) {
				byte lc = geo.get(index);
				index += (lc << 1) + 1;
				offset--;
			}
			byte layers = geo.get(index);
			index++;
			short height = -1;
			if (layers <= 0 || layers > 125) {
				_log.warning("Broken geofile (case1), region: " + region
						+ " - invalid layer count: " + layers + " at: " + geox
						+ " " + geoy);
				return (short) z;
			}
			short temph = Short.MIN_VALUE;
			while (layers > 0) {
				height = geo.getShort(index);
				height = (short) (height & 0x0fff0);
				height = (short) (height >> 1); // height / 2
				if ((z - temph) * (z - temph) > (z - height) * (z - height))
					temph = height;
				layers--;
				index += 2;
			}
			return temph;
		}
	}

	/**
	 * @param x
	 * @param y
	 * @param zmin
	 * @param zmax
	 * @return Z betwen zmin and zmax
	 */
	private static short nGetSpawnHeight(int geox, int geoy, int zmin,
			int zmax, int spawnid) {
		short region = getRegionOffset(geox, geoy);
		int blockX = getBlock(geox);
		int blockY = getBlock(geoy);
		int cellX, cellY, index;
		short temph = Short.MIN_VALUE;
		// Geodata without index - it is just empty so index can be calculated
		// on the fly
		if (_geodataIndex.get(region) == null)
			index = ((blockX << 8) + blockY) * 3;
		// Get Index for current block of current region geodata
		else
			index = _geodataIndex.get(region).get((blockX << 8) + blockY);
		// Buffer that Contains current Region GeoData
		ByteBuffer geo = _geodata.get(region);
		if (geo == null) {
			if (Config.DEBUG)
				_log.warning("Geo Region - Region Offset: " + region
						+ " dosnt exist!!");
			return (short) zmin;
		}
		// Read current block type: 0-flat,1-complex,2-multilevel
		byte type = geo.get(index);
		index++;
		if (type == 0)
			temph = geo.getShort(index);
		else if (type == 1)// complex
		{
			cellX = getCell(geox);
			cellY = getCell(geoy);
			index += (cellX << 3) + cellY << 1;
			short height = geo.getShort(index);
			height = (short) (height & 0x0fff0);
			height = (short) (height >> 1); // height / 2
			temph = height;
		} else
		// multilevel
		{
			cellX = getCell(geox);
			cellY = getCell(geoy);
			short height;
			int offset = (cellX << 3) + cellY;
			while (offset > 0) {
				byte lc = geo.get(index);
				index += (lc << 1) + 1;
				offset--;
			}
			// Read current block type: 0-flat,1-complex,2-multilevel
			byte layers = geo.get(index);
			index++;
			if (layers <= 0 || layers > 125) {
				_log.warning("Broken geofile (case2), region: " + region
						+ " - invalid layer count: " + layers + " at: " + geox
						+ " " + geoy);
				return (short) zmin;
			}
			while (layers > 0) {
				height = geo.getShort(index);
				height = (short) (height & 0x0fff0);
				height = (short) (height >> 1); // height / 2
				if ((zmin - temph) * (zmin - temph) > (zmin - height)
						* (zmin - height))
					temph = height;
				layers--;
				index += 2;
			}
			if (temph > zmax + 200 || temph < zmin - 200) {
				if (Config.DEBUG)
					_log.warning("SpawnHeight Error - Couldnt find correct layer to spawn NPC - GeoData or Spawnlist Bug!: zmin: "
							+ zmin
							+ " zmax: "
							+ zmax
							+ " value: "
							+ temph
							+ " SpawnId: "
							+ spawnid
							+ " at: "
							+ geox
							+ " : "
							+ geoy);
				return (short) zmin;
			}
		}
		if (temph > zmax + 1000 || temph < zmin - 1000) {
			if (Config.DEBUG)
				_log.warning("SpawnHeight Error - Spawnlist z value is wrong or GeoData error: zmin: "
						+ zmin
						+ " zmax: "
						+ zmax
						+ " value: "
						+ temph
						+ " SpawnId: "
						+ spawnid
						+ " at: "
						+ geox
						+ " : "
						+ geoy);
			return (short) zmin;
		}
		return temph;
	}

	/**
	 * @param x
	 * @param y
	 * @param z
	 * @param tx
	 * @param ty
	 * @param tz
	 * @return True if char can move to (tx,ty,tz)
	 */
	private static double nCanMoveNext(int x, int y, int z, int tx, int ty,
			int tz) {
		short region = getRegionOffset(x, y);
		int blockX = getBlock(x);
		int blockY = getBlock(y);
		int cellX, cellY;
		short NSWE = 0;
		int index = 0;
		// Geodata without index - it is just empty so index can be calculated
		// on the fly
		if (_geodataIndex.get(region) == null)
			index = ((blockX << 8) + blockY) * 3;
		// Get Index for current block of current region geodata
		else
			index = _geodataIndex.get(region).get((blockX << 8) + blockY);
		// Buffer that Contains current Region GeoData
		ByteBuffer geo = _geodata.get(region);
		if (geo == null) {
			if (Config.DEBUG)
				_log.warning("Geo Region - Region Offset: " + region
						+ " dosnt exist!!");
			return z;
		}
		// Read current block type: 0-flat,1-complex,2-multilevel
		byte type = geo.get(index);
		index++;
		if (type == 0)
			return z;
		else if (type == 1) // complex
		{
			cellX = getCell(x);
			cellY = getCell(y);
			index += (cellX << 3) + cellY << 1;
			short height = geo.getShort(index);
			NSWE = (short) (height & 0x0F);
			height = (short) (height & 0x0fff0);
			height = (short) (height >> 1); // height / 2
			if (checkNSWE(NSWE, x, y, tx, ty))
				return height;
			else
				return Double.MIN_VALUE;
		} else
		// multilevel, type == 2
		{
			cellX = getCell(x);
			cellY = getCell(y);
			int offset = (cellX << 3) + cellY;
			while (offset > 0) // iterates (too many times?) to get to layer
								// count
			{
				byte lc = geo.get(index);
				index += (lc << 1) + 1;
				offset--;
			}
			byte layers = geo.get(index);
			// _log.warning("layers"+layers);
			index++;
			short height = -1;
			if (layers <= 0 || layers > 125) {
				_log.warning("Broken geofile (case3), region: " + region
						+ " - invalid layer count: " + layers + " at: " + x
						+ " " + y);
				return z;
			}
			short tempz = Short.MIN_VALUE;
			while (layers > 0) {
				height = geo.getShort(index);
				height = (short) (height & 0x0fff0);
				height = (short) (height >> 1); // height / 2
				// searches the closest layer to current z coordinate
				if ((z - tempz) * (z - tempz) > (z - height) * (z - height)) {
					// layercurr = layers;
					tempz = height;
					NSWE = geo.getShort(index);
					NSWE = (short) (NSWE & 0x0F);
				}
				layers--;
				index += 2;
			}
			if (checkNSWE(NSWE, x, y, tx, ty))
				return tempz;
			else
				return Double.MIN_VALUE;
		}
	}

	/**
	 * @param x
	 * @param y
	 * @param z
	 * @param inc_x
	 * @param inc_y
	 * @param tz
	 * @return True if Char can see target
	 */
	private static boolean nLOS(int x, int y, int z, int inc_x, int inc_y,
			int tz, boolean debug) {
		short region = getRegionOffset(x, y);
		int blockX = getBlock(x);
		int blockY = getBlock(y);
		int cellX, cellY;
		short NSWE = 0;
		int index;
		// Geodata without index - it is just empty so index can be calculated
		// on the fly
		if (_geodataIndex.get(region) == null)
			index = ((blockX << 8) + blockY) * 3;
		// Get Index for current block of current region geodata
		else
			index = _geodataIndex.get(region).get((blockX << 8) + blockY);
		// Buffer that Contains current Region GeoData
		ByteBuffer geo = _geodata.get(region);
		if (geo == null) {
			if (Config.DEBUG)
				_log.warning("Geo Region - Region Offset: " + region
						+ " dosnt exist!!");
			return true;
		}
		// Read current block type: 0-flat,1-complex,2-multilevel
		byte type = geo.get(index);
		index++;
		if (type == 0) // flat, movement and sight always possible
		{
			if (debug)
				_log.warning("flatheight:" + geo.getShort(index));
			return true;
		} else if (type == 1) // complex
		{
			cellX = getCell(x);
			cellY = getCell(y);
			index += (cellX << 3) + cellY << 1;
			short height = geo.getShort(index);
			NSWE = (short) (height & 0x0F);
			height = (short) (height & 0x0fff0);
			height = (short) (height >> 1); // height / 2
			if (debug) {
				_log.warning("height:" + height + " z" + z);
				if (!checkNSWE(NSWE, x, y, x + inc_x, y + inc_y))
					_log.warning("would block");
			}
			if (z - height > 50)
				return true; // this value is just an approximate
		} else
		// multilevel, type == 2
		{
			cellX = getCell(x);
			cellY = getCell(y);
			int offset = (cellX << 3) + cellY;
			while (offset > 0) // iterates (too many times?) to get to layer
								// count
			{
				byte lc = geo.get(index);
				index += (lc << 1) + 1;
				offset--;
			}
			byte layers = geo.get(index);
			if (debug)
				_log.warning("layers" + layers);
			index++;
			short height = -1;
			if (layers <= 0 || layers > 125) {
				_log.warning("Broken geofile (case4), region: " + region
						+ " - invalid layer count: " + layers + " at: " + x
						+ " " + y);
				return false;
			}
			short tempz = Short.MIN_VALUE; // big negative value
			byte temp_layers = layers;
			boolean highestlayer = true;
			z -= 25; // lowering level temporarily to avoid selecting ceiling
			while (temp_layers > 0) {
				// reads height for current layer, result in world z coordinate
				height = geo.getShort(index);
				height = (short) (height & 0x0fff0);
				height = (short) (height >> 1); // height / 2
				// height -= 8; // old geo files had -8 around giran, new data
				// seems better
				// searches the closest layer to current z coordinate
				if ((z - tempz) * (z - tempz) > (z - height) * (z - height)) {
					if (tempz > Short.MIN_VALUE)
						highestlayer = false;
					tempz = height;
					if (debug)
						_log.warning("z" + (z + 45) + " tempz" + tempz + " dz"
								+ (z - tempz));
					NSWE = geo.getShort(index);
					NSWE = (short) (NSWE & 0x0F);
				}
				temp_layers--;
				index += 2;
			}
			z += 25; // level rises back
			// Check if LOS goes under a layer/floor
			if (z - tempz < -20)
				return false; // -20 => clearly under, approximates also fence
								// width
			// this helps in some cases (occasional under-highest-layer block
			// which isn't wall)
			// but might also create problems in others (passes walls when
			// you're standing high)
			if (z - tempz > 250)
				return true;
			// or there's a fence/wall ahead when we're not on highest layer
			// this part of the check is problematic
			if (!highestlayer) {
				// a probable wall, there's movement block and layers above you
				if (!checkNSWE(NSWE, x, y, x + inc_x, y + inc_y)) // cannot move
				{
					// the height after 2 inc_x,inc_y
					short nextheight = nGetHeight(x + 2 * inc_x, y + 2 * inc_y,
							z - 50);
					if (debug) {
						_log.warning("0: z:" + z + " tz"
								+ nGetHeight(x, y, z - 60));
						_log.warning("1: z:" + z + " tz"
								+ nGetHeight(x + inc_x, y + inc_y, z - 60));
						_log.warning("2: z:"
								+ z
								+ " tz"
								+ nGetHeight(x + 2 * inc_x, y + 2 * inc_y,
										z - 60));
						_log.warning("3: z:"
								+ z
								+ " tz"
								+ nGetHeight(x + 3 * inc_x, y + 3 * inc_y,
										z - 60));
					}
					// Probably a very thin fence (e.g. castle fences above
					// artefact),
					// where height instantly drops after 1-2 cells and layer
					// ends.
					if (z - nextheight > 100)
						return true;
					// layer continues so close we can see over it
					if (nextheight - tempz > 5 && nextheight - tempz < 20)
						return true;
					return false;
				} else
					return true;
			} else
				return true;
		}
		return checkNSWE(NSWE, x, y, x + inc_x, y + inc_y);
	}

	/**
	 * @param x
	 * @param y
	 * @param z
	 * @return NSWE: 0-15
	 */
	private short nGetNSWE(int x, int y, int z) {
		short region = getRegionOffset(x, y);
		int blockX = getBlock(x);
		int blockY = getBlock(y);
		int cellX, cellY;
		short NSWE = 0;
		int index = 0;
		// Geodata without index - it is just empty so index can be calculated
		// on the fly
		if (_geodataIndex.get(region) == null)
			index = ((blockX << 8) + blockY) * 3;
		// Get Index for current block of current region geodata
		else
			index = _geodataIndex.get(region).get((blockX << 8) + blockY);
		// Buffer that Contains current Region GeoData
		ByteBuffer geo = _geodata.get(region);
		if (geo == null) {
			if (Config.DEBUG)
				_log.warning("Geo Region - Region Offset: " + region
						+ " dosnt exist!!");
			return 15;
		}
		// Read current block type: 0-flat,1-complex,2-multilevel
		byte type = geo.get(index);
		index++;
		if (type == 0)
			return 15;
		else if (type == 1)// complex
		{
			cellX = getCell(x);
			cellY = getCell(y);
			index += (cellX << 3) + cellY << 1;
			short height = geo.getShort(index);
			NSWE = (short) (height & 0x0F);
		} else
		// multilevel
		{
			cellX = getCell(x);
			cellY = getCell(y);
			int offset = (cellX << 3) + cellY;
			while (offset > 0) {
				byte lc = geo.get(index);
				index += (lc << 1) + 1;
				offset--;
			}
			byte layers = geo.get(index);
			index++;
			short height = -1;
			if (layers <= 0 || layers > 125) {
				_log.warning("Broken geofile (case5), region: " + region
						+ " - invalid layer count: " + layers + " at: " + x
						+ " " + y);
				return 15;
			}
			short tempz = Short.MIN_VALUE;
			while (layers > 0) {
				height = geo.getShort(index);
				height = (short) (height & 0x0fff0);
				height = (short) (height >> 1); // height / 2
				if ((z - tempz) * (z - tempz) > (z - height) * (z - height)) {
					tempz = height;
					NSWE = geo.get(index);
					NSWE = (short) (NSWE & 0x0F);
				}
				layers--;
				index += 2;
			}
		}
		return NSWE;
	}

	/**
	 * @param NSWE
	 * @param x
	 * @param y
	 * @param tx
	 * @param ty
	 * @return True if NSWE dont block given direction
	 */
	private static boolean checkNSWE(short NSWE, int x, int y, int tx, int ty) {
		// Check NSWE
		if (NSWE == 15)
			return true;
		if (tx > x)
			if ((NSWE & _e) == 0)
				return false;
		if (tx < x)
			if ((NSWE & _w) == 0)
				return false;
		if (ty > y)
			if ((NSWE & _s) == 0)
				return false;
		if (ty < y)
			if ((NSWE & _n) == 0)
				return false;
		return true;
	}
}
